#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/9/19 09:20
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 中级-在排序数组中查找元素的第一个和最后一个位置.py
# @Software: PyCharm


class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        ans = []
        n = len(nums)
        l = 0
        r = n - 1
        while l < r:
            m = (l+r)//2
            if nums[m] >= target:
                r = m
            else:
                l = m + 1
        if l < 0 or l >= n or nums[l] != target:
            return [-1, -1]
        ans.append(l)
        l = 0
        r = n-1
        while l < r:
            m = (l+r)//2
            if nums[m] > target:
                r = m - 1
            else:
                l = m + 1
        if l > 1 and nums[l] != target:
            l -= 1
        ans.append(l)
        return ans


def main():
    solve = Solution()
    nums = [5, 7, 7, 8, 8, 8, 10]
    nums = [5, 7, 7, 8, 8, 10]
    target = 8
    # nums = [2, 2]
    # target = 2
    print('problem:', nums, target)
    ans = solve.searchRange(nums, target)
    print('ans:', ans)


if __name__ == '__main__':
    main()
